package str;

import java.util.HashMap;

/**
 * 无重复字符的最长子串【长度】
 * 思路：滑动窗口，而且只是要求长度，没有求子串是什么，所以难度降低了，
 * 这个解法是在不好理解的写法里面解决特殊情况，虽然很简洁，但是不太好
 */
public class Lt3 {

    public int lengthOfLongestSubstring(String s) {
        // 必须有个结构用来检测有无重复，为了方便可以直接使用集合，
        // 这里用map取巧的地方是，同时记录字符下标，方便跳转
        HashMap<Character, Integer> map = new HashMap<>();

        int max = 0, start = 0;

        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)) {
                // 如果找到了重复的字符，就把子串起始位往右移一位，那么直接map.get(ch) + 1就行了对不对？这样其实是有问题的
                // 思考耗时mark
                // 解释：是为了处理：【出现了重复的新key，但这个key没有出现在当前窗口的字符串中】的情况，这种情况是小于start的，
                // 例如hjkjabch，end到了最后的h，此时start在k位，值为2，而map.get('h') + 1会得到1，小于start
                // 如果没看明白，心里执行一下流程
                start = Math.max(map.get(ch) + 1, start);
            }
            // 这里取大是为了解决abcdefghhh的情况，
            max = Math.max(max, end - start + 1);
            // 每次都把字符和下标存储好，对于重复的字符会更新下标
            map.put(ch, end);
        }
        return max;
    }

}
